/**
 * 一个矩形，横着可以且m-1刀，竖着可以且n-1刀，各有代价
 * 问切成单位正方形，最小代价是多少
 * C题的hard版，n和m在1E5。
 * 跟C题一样，首先有一个贪心，在横竖内部，代价越高的位置越要先切
 * 然后再考虑横刀和竖刀谁应该排在前面。使用典型的交换验证即可，因为显然具有传递性。
 * 也就是说只考虑当前的两刀，先横后竖，再先竖后横，比较一下即可。完全无需考虑其他刀。
 * O(NlogN)可以解决
 */
class Solution {
struct _t{
    long long v;
    int row_idx;
    int col_idx;
    bool operator < (const _t & b) const {
        if(row_idx == b.row_idx or col_idx == b.col_idx){
            if(v != b.v) return v > b.v;
            if(row_idx) return row_idx < b.row_idx;
            return col_idx < b.col_idx;
        }

        long long ca, cb;
        if(row_idx){
            ca = v * (b.col_idx) + b.v * (row_idx + 1);
            cb = b.v * row_idx + v * (b.col_idx + 1);            
        }else{
            ca = v * b.row_idx + b.v * (col_idx + 1);
            cb = b.v * col_idx + v * (b.row_idx + 1);
        }
        if(ca != cb) return ca < cb;
        if(row_idx) return row_idx > b.col_idx;
        if(col_idx) return col_idx > b.row_idx;
        return false;
    }
};    

vector<vector<int>> D;

public:
    long long minimumCost(int m, int n, vector<int>& horizontalCut, vector<int>& verticalCut) {
        using llt = long long;
        static const llt INF = 0x7F6F7F8F1F2F3F4F;

        sort(horizontalCut.begin(), horizontalCut.end(), greater<int>());
        sort(verticalCut.begin(), verticalCut.end(), greater<int>());
        
        vector<_t> vec;
        for(int i=0;i<horizontalCut.size();++i){
            vec.push_back({horizontalCut[i],i + 1, 0});
        }
        for(int i=0;i<verticalCut.size();++i){
            vec.push_back({verticalCut[i], 0, i + 1});
        }
        sort(vec.begin(), vec.end());

        llt ans = 0;
        int r = 1, c = 1;
        for(const auto & p : vec){
            if(p.row_idx){
                ans += p.v * c;
                r += 1;
            }else{
                ans += p.v * r;
                c += 1;
            }
        }

        return ans;
    }
};